//树：非线性的数据结构，以分层的方式存储数据
//有一组以边连接的节点组成，
//二叉树是一种特殊的树，它的子节点个数不超过两个，从一个节点到另一个节点的边城为路径，
//有三种遍历方式
//先序（根左右），中序（左根右），后序（左右根）
//二叉树的插入
//先创建一个node节点【这个节点包含了left，right，data】
//判断当前节点是否为一棵新树，新书第一个插入的节点为根节点，否则进行判断，看他要插到哪里
//如果不是一棵新树，根的做节点与newNOde比较，如果是那就从左子树遍历，再判断左子树是否有值
//没值就插入，有值就继续遍历
//如果数据小于newNode数据，那就从右子树遍历，和左子树遍历是一样的，

//实现查找树：
//查找最小值，那就是遍历左子树，一直找最后一个左子树，
//查找最大值，那就遍历右子树，一直找最后一个右子树，
function Node(data,left,right){
    this.data=data;
    this.left=left;
    this.right=right;
    this.show=show;
}

function show(){
    return this.data;
}

function BST(){
    this.root=null;
    this.insert=insert;
    this.inOrderMid=inOrderMid;
    this.inOrderPre=inOrderPre;
    this.inOrderLast=inOrderLast;
    this.getMin=getMin;
    this.getMax=getMax;
    this.find=find;
    this.remove=remove;
    this.removeNode=removeNode;
}

function insert(data){
    var n=new Node(data,null,null);
    if(this.root===null){
        this.root=n;
    }else{
        var current=this.root;
        var parent;
        while(true){
            parent=current;
            if(data<current.data){
                current=current.left;
                if(current===null){
                    parent.left=n;
                    break;
                }
            }else{
                current=current.right;
                if(current===null){
                    parent.right=n;
                    break;
                }
            }
        }
    }
}
//中序遍历
function inOrderMid(node){
    if(!(node===null)){
        inOrderMid(node.left);
        console.log(node.show()+" ");
        inOrderMid(node.right);
    }
}
//先序遍历
function inOrderPre(node){
    if(!(node===null)){
        console.log(node.show()+" ");
        inOrderPre(node.left);
        inOrderPre(node.right);
    }
}
//后序遍历
function inOrderLast(node){
    if(!(node===null)){
        inOrderLast(node.left);
        inOrderLast(node.right);
        console.log(node.show()+" ");
    }
}
//找节点问题
//需要和当前元素比较，先判断是做遍历还是右遍历，
// 先判断当节点不为空，比较是否相等，想等的话：返回当前节点，不等的话看是大还是小，决定左遍历还是右遍历，没找到就返回null；
function find(data){
    var current=this.root;
    while(current!==null){
        if(current.data===data){
            return current;
        }else if(data<current.data){
            current=current.left;
        }else{
            current=current.right;
        }
    }
    return null;
}
function getMin(){
    var current=this.root;
    while(!(current.left===null)){
        current=current.left;
    }
    return current.data;
}
function getMax(){
    var current=this.root;
    while(!(current.right===null)){
        current=current.right;
    }
    return current.data;
}

//删除节点！！难爆了
//原理：先从二叉树上找到该节点，
// 第一：判断当前述据是否find数据，不是则继续比较，小于则遍历左子树，大则遍历右子树
//第二：delete是叶子结点，无左右子树，让他的parent指向null；
//第三：删除包括一个子节点，删了他，让他的指向他的指针指向他的子树；
//删除有左右子树的数据：如果当前root为空，则无data返回
//如果data=node，先判断是否有子节点，都没返回null,有左子树返回左子树，有右子树返回右子树，有两个子树就要判断
//我的思路：先找到该店判断该节点是否有左右子树，没有则直接让指向他的指针指向空，you左子树，就指向左子树，有右子树就指向
//右子树，you左右子树：判断
function remove(data){
    root=removeNode(this.root,data);
}
function removeNode(node,data){
    if(node===null){
        return null;
    }
    if(data===node.data){
        //没有子节点
        if(node.left===null&&node.right===null){
            return null;
        }
        //没有左子节点的节点
        if(node.left===null){
            return node.left;
        }
        //没有右子节点
        if(node.right===null){
            return node.left;
        }
        var tempNode=getSmallest(node.right);
        node.data=tempNode.data;
        node.right=removeNode(node.right,tempNode.data);
        return node;
    }else if(data<node.data){
        node.left=removeNode(node.left,data);
        return node;
    }else{
        node.right=removeNode(node.right,data);
        return node;
    }
}
function getSmallest(node){
    var current=node;
    while(!(current.left===null)){
        current=current.left;
    }
    return current.data;
}
var nums=new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
var max=nums.getMax();
var min=nums.getMin();
console.log(max);
console.log(min);
var found=nums.find(22);
console.log(found);
inOrderLast(nums.root);

console.log("\n");
inOrderPre(nums.root);
console.log("\n");
inOrderMid(nums.root);
console.log("\n");
nums.remove(22);
inOrderMid(nums.root);